package cn.skyjilygao.leetcode;

/**
 * 题目：颠倒给定的 32 位无符号整数的二进制位。
 * <p> 说明：
 * <br> 1. 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
 * <br> 2. 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。
 * <p>
 * <p>
 * <br>
 * <p>
 * <p> Leetcode题: <a href="https://leetcode-cn.com/problems/reverse-bits"> 190. 颠倒二进制位 </a>
 *
 * @author skyjilygao
 * @date 20201028
 */
public class ReverseBits {
    public static void main(String[] args) {
         int n = 43261596;
        System.out.println(reverseBits(n));
    }

    /**
     * 思路1：位运算合并
     * <p> 说明：例如：0111 1001 0010 1101   0011 1101 1111 1010
     * <p>
     * <p> 1. 每16位一组交换
     * <br> 1.1. 左边16位右移16位: 0000 0000 0000 0000   0111 1001 0010 1101
     * <br> 1.2. 右边16位左移16位P: 0011 1101 1111 1010   0000 0000 0000 0000
     * <br> 合并（或运算）：0011 1101 1111 1010   0111 1001 0010 1101
     * <br> 所以：每16位一组交换公式：n = n >>> 16 | n << 16
     *
     * <p> 2. 每8位一组交换：从左至右：第一个8位，跟第二个8位交换；第三个8位跟第四个8位交换
     * <br> 因为合并结果就是要保证合并前与合并后非0位置的值保持不变，那么就要保证另一组相应位置为0。例如：0110 与 xxxx合并结果为0110，那么xxxx就一定是0000
     * <br> 反向推导过程：
     * <br> 2.1. 本次交换结果：1111 1010 0011 1101   0010 1101 0111 1001
     * <br> 合并前的2组数据：
     * <br> 1111 1010 0000 0000   0010 1101 0000 0000
     * <br> 0000 0000 0011 1101   0000 0000 0111 1001
     * <br> 2.2. 因为是每8位一组交换，所以对于“1111 1010 0000 0000   0010 1101 0000 0000”
     * <br> 右移8位前应该是：0000 0000 1111 1010   0000 0000 0010 1101
     * <br> 那么由步骤1结果“0011 1101 1111 1010   0111 1001 0010 1101” 变成 “0000 0000 1111 1010   0000 0000 0010 1101”的方式可以使用位与运算
     * <br> 0011 1101 1111 1010   0111 1001 0010 1101 与 0000 0000 1111 1111   0000 0000 1111 1111 即：0011 1101 1111 1010   0111 1001 0010 1101 & 0x00ff00ff
     * <br> 2.3. 因为是每8位一组交换，所以对于“0000 0000 0011 1101   0000 0000 0111 1001”
     * <br> 左移8位前应该是：0011 1101 0000 0000   0111 1001 0000 0000
     * <br> 那么由步骤1结果“0011 1101 1111 1010   0111 1001 0010 1101” 变成 “1111 1010 0000 0000   0010 1101 0000 0000”的方式可以使用位与运算
     * <br> 0011 1101 1111 1010   0111 1001 0010 1101 与 1111 1111 0000 0000   1111 1111 0000 0000 即：0011 1101 1111 1010   0111 1001 0010 1101 & 0xff00ff00
     * <br> 所以：每8位一组交换公式：n = ((n & 0x00ff00ff) << 8) | ((n & 0xff00ff00) >>> 8)
     *
     * <p> 3. 每4位一组交换：从左至右：第一个4位，跟第二个4位交换；第三个4位跟第四个4位交换；第五个5位跟第六个4位交换；第七个4位跟第八个4位交换
     * <br> 重复步骤2推到过程，得知
     * <br> 每4位一组交换公式：n = ((n & 0000 1111 0000 1111   0000 1111 0000 1111) << 4) | ((n & 1111 0000 1111 0000   1111 0000 1111 0000) >>> 4) 即 n = ((n & 0x0f0f0f0f) << 4) | ((n & 0xf0f0f0f0) >>> 4)
     *
     * <p> 4. 每2位一组交换：从左至右：1(2) 交换 2(2); 3(2) 交换 4(2); 5(2) 交换 6(2); 7(2) 交换 8(2); 9(2) 交换 10(2); 11(2) 交换 12(2); 13(2) 交换 14(2); 15(2) 交换 16(2);
     * <br> 重复步骤2推到过程，得知
     * <br> 每2位一组交换公式：n = ((n & 0011 0011 0011 0011   0011 0011 0011 0011) << 2) | ((n & 1100 1100 1100 1100   1100 1100 1100 1100) >>> 2) 即 n = ((n & 0x33333333) << 2) | ((n & 0xcccccccc) >>> 2)
     *
     * <p> 5. 每1位一组交换：第一位跟第二位交换，第三位跟第四位交换；...... 第31位跟第32位交换
     * <br> 重复步骤2推到过程，得知
     * <br> 每1位一组交换公式：n = ((n & 0101 0101 0101 0101   0101 0101 0101 0101) << 2) | ((n & 1010 1010 1010 1010   1010 1010 1010 1010) >>> 2) 即 n = ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >>> 1)
     * <p> 最终交换公式：
     * <br> n = n >>> 16 | n << 16
     * <br> n = ((n & 0x00ff00ff) << 8) | ((n & 0xff00ff00) >>> 8)
     * <br> n = ((n & 0x0f0f0f0f) << 4) | ((n & 0xf0f0f0f0) >>> 4)
     * <br> n = ((n & 0x33333333) << 2) | ((n & 0xcccccccc) >>> 2)
     * <br> n = ((n & 0x55555555) << 1) | ((n & 0xaaaaaaaa) >>> 1)
     *
     * <p>
     * <p> 参考: https://leetcode-cn.com/problems/reverse-bits/solution/zhi-qi-ran-zhi-qi-suo-yi-ran-wei-yun-suan-jie-fa-x/ 中的解法3，说的很详细。
     * <p>
     * <p> 多次执行耗时：
     * <br> 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * <br> 内存消耗：38.2 MB, 在所有 Java 提交中击败了87.57%的用户
     *
     * @param n
     * @return
     */
    public static int reverseBits(int n) {
        // 左边都是无符号位运算
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
        n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
        n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
        return n;

    }
}
